1. Field of the Invention
The present invention relates to a decoding method, decoding apparatus and digital transmission system of a product code for improving the reliability of a digital communication system or digital recording system.
2. Description of Related Art
Although error-correcting codes such as Reed-Solomon codes have been utilized to improve reliability of digital communication/recording systems, more powerful error-correcting codes have been required recently to meet increasing speed and capacity of the systems.
In general, high performance correcting codes require complicated decoding, which makes it difficult to be built into an apparatus. However, using concatenated codes or product codes makes it possible to implement high-performance coding rather easily. In particular, the product codes have an advantage that they have large redundancy and error-correcting power because of the double encoding of information data. Accordingly, they are applied as an error-correcting method of CD-ROMs and DVDs.
FIG. 9 is a diagram showing a construction of a product code. In FIG. 9, a code in the vertical direction is a binary linear code C1 with a code length N1 and information length K1, and a code in the horizontal direction is a binary linear code C2 with a code length N2 and information length K2. The block 1 designates information data, and blocks 24 each designate checks (redundant checks).
Next, an encoding method of the product code will be described with reference to FIG. 9.
First, K1×K2-bit information data are stored in the two-dimensional array (block 1) with K1 rows and K2 columns. The block 1 is represented by the following Expression (1), where Di,j (i=1, 2, . . . , K1; j=1, 2, . . . , K2) is 0 or 1.
                              [                                                                      D                                      1                    ,                    1                                                                                                D                                      1                    ,                    2                                                                              ⋯                                                              D                                      1                    ,                    K2                                                                                                                        D                                      2                    ,                    1                                                                                                D                                      2                    ,                    2                                                                              ⋯                                                              D                                      2                    ,                    K2                                                                                                      ⋮                                            ⋮                                            ⋰                                            ⋮                                                                                      D                                      K1                    ,                    1                                                                                                D                                      K1                    ,                    2                                                                              ⋯                                                              D                                      K1                    ,                    K2                                                                                ]                ⁢                  (                                                    D                                  i                  ,                  j                                            =              0                        ,            1                    )                                    (        1        )            
Next, individual columns from the first to K2th column are provided with (N1−K1)-bit checks of the C1 code to construct a two-dimensional array with N1-rows and K2-columns (construction of the block 2). Subsequently, individual rows from the first to N1th row are provided with (N2−K2)-bit checks of the C2 code to construct a two-dimensional array with N1-rows and N2-columns (construction of the blocks 3 and 4).
FIG. 10 is a block diagram showing a configuration of a conventional digital transmission system utilizing a product code, which is disclosed in Japanese patent application laid-open No. 7-202722, for example. In FIG. 10, the reference numeral 1 designates an encoder for encoding input information data to generate a product code; 2 designates a modulator for converting the product code generated by the encoder 1 into a signal suitable for a communication channel 3; 3 designates the communication channel; 4 designates a demodulator for demodulating a received signal sent via the communication channel 3 and for supplying the demodulated data to a decoder 5; and 5 designates the decoder for decoding the demodulated data supplied from the demodulator 4 to estimate the information data. The encoder 1 and modulator 2 constitute a transmitter, and the demodulator 4 and the decoder 5 constitute a receiver.
Next, the operation of the system as shown in FIG. 10 will be described.
The input K1×K2-bit information data are supplied to the encoder 1 for generating the product code with N1 rows and N2 columns. The product code generated is represented by a matrix C of the following Expression (2). Although the elements of the product code C is represented by the binary 0 or 1, the binary 0 is represented as “+1”, and the binary 1 is represented by “−1” in the following.
                    C        =                              [                                                                                C                                          1                      ,                      1                                                                                                            C                                          1                      ,                      2                                                                                        ⋯                                                                      C                                          1                      ,                      N2                                                                                                                                        C                                          2                      ,                      1                                                                                                            C                                          2                      ,                      2                                                                                        ⋯                                                                      C                                          2                      ,                      N2                                                                                                                    ⋮                                                  ⋮                                                  ⋰                                                  ⋮                                                                                                  C                                          N1                      ,                      1                                                                                                            C                                          N1                      ,                      2                                                                                        ⋯                                                                      C                                          N1                      ,                      N2                                                                                            ]                    ⁢                      (                                          C                                  i                  ,                  j                                            =                              ±                1                                      )                                              (        2        )            
The product code generated by the encoder 1 is supplied to the modulator 2 to be converted into the signal suitable for the communication channel 3, and is transmitted through the communication channel 3. It is assumed as to the communication channel 3 that additive noise is superimposed on a transmission signal. The signal received through the communication channel 3 is supplied to the demodulator 4 of the receiver.
The demodulator 4 carries out shaping of the received signal to generate the demodulated data Y given by the following Expression (3). The components of the matrix Y are represented as Yi,j=Ci,j+Ni,j, where Ni,j are noise components. The demodulated data Y generated by the demodulator 4 is supplied to the decoder 5 for estimating the transmitted information data.
                    Y        =                              [                                                                                Y                                          1                      ,                      1                                                                                                            Y                                          1                      ,                      2                                                                                        ⋯                                                                      Y                                          1                      ,                      N2                                                                                                                                        Y                                          2                      ,                      1                                                                                                            Y                                          2                      ,                      2                                                                                        ⋯                                                                      Y                                          2                      ,                      N2                                                                                                                    ⋮                                                  ⋮                                                  ⋰                                                  ⋮                                                                                                  Y                                          N1                      ,                      1                                                                                                            Y                                          N1                      ,                      2                                                                                        ⋯                                                                      Y                                          N1                      ,                      N2                                                                                            ]                    .                                    (        3        )            
In the following description, a matrix is represented by braces such as {Y} and a vector is represented by square brackets such as [V]. Thus, the demodulated data Y of the foregoing Expression (3) is denoted by {Y}, and is referred to as an input matrix. The first column (N1 vector) is denoted by [Vk,1], and to specify the range of the suffix k, it is represented as [Vk,1] (k=1, 2, . . . , N1).
FIG. 11 is a flowchart illustrating the operation of the decoder 5. In FIG. 11, ST1 is a step of inputting the input matrix {Y}; ST2 is a step of setting initial values into a correction matrix {W} and a decision matrix {D}; ST3 is a step of setting an initial value into a counter j; ST4 is a step of calculating a soft input vector [Rk](k=1, 2, . . . , N1); ST5 is a step of calculating a soft output vector [Lk] (k=1, 2, . . . , N1); ST6 is a step of updating a correction matrix {W}; ST7 is a step of comparing the value of the counter j; and ST8 is a step of incrementing the value of the counter j.
In addition, ST9 is a step of setting an initial value into a counter i; ST10 is a step of calculating a soft input vector [Rk] (k=1, 2, . . . , N2); ST11 is a step of calculating a soft output vector [Lk](k=1, 2, . . . , N2); ST12 is a step of updating the correction matrix {W}; ST13 is a step of comparing the value of the counter i; ST14 is a step of incrementing the value of the counter i; ST15 is a step of making a decision as to whether to iterate the decoding of the product code; and ST16 is a step of outputting the decision matrix {D}.
Next, the operation of the decoder 5 will be described in more detail with reference to the flowchart of FIG. 11. First, at step ST1, the N1×N2 input matrix {Y} given by the foregoing Expression (3) is input. At the next step ST2, the initial value zero is stored into all the elements of the N1×N2 correction matrix {W} given by the following Expression (4).
                    W        =                  [                                                                      W                                      1                    ,                    1                                                                                                W                                      1                    ,                    2                                                                              ⋯                                                              W                                      1                    ,                    N2                                                                                                                        W                                      2                    ,                    1                                                                                                W                                      2                    ,                    2                                                                              ⋯                                                              W                                      2                    ,                    N2                                                                                                      ⋮                                            ⋮                                            ⋰                                            ⋮                                                                                      W                                      N1                    ,                    1                                                                                                W                                      N1                    ,                    2                                                                              ⋯                                                              W                                      N1                    ,                    N2                                                                                ]                                    (        4        )            
Furthermore, initial values sgn{Y} are stored into all the elements of the N1×N2 decision matrix {D}. Specifically, the (i,j) elements Di,j of the decision matrix {D} is replaced by the code sgn(Yi,j) of the (i,j) elements Yi,j of the input matrix {Y}, where sgn is a function defined by the following Expression (5).
                              sgn          ⁡                      (            x            )                          =                  {                                                                                          +                    1                                    ⁢                                      (                                          x                      ≥                                                                                          ⁢                      0                                        )                                                                                                                                            -                    1                                    ⁢                                      (                                          x                      <                      0                                        )                                                                                                          (        5        )            
At step ST3, the initial value one is set into the counter j. At the next step ST4, decoding of the C1 code is started.
At step ST4, jth column of the input matrix {Y} and the jth column of the correction matrix {W} are added element by element. Specifically, according to the following Expression (6), the (k,j) elements Yk,j of the input matrix {Y} are added to the (k,j) elements Wk,j of the correction matrix {W} to calculate the soft input values Rk (k=1, 2, . . . , N1).Rk←Yk,j+α×Wk,j(k=1, 2, . . . , N1)  (6)where α is an appropriate normalizing constant.
In the following description, the jth column of the input matrix is denoted by [Yk,j], that of the decision matrix is denoted by [Dk,j], and that of the correction matrix is denoted by [Wk,j], which are called input vector, decision vector and correction vector, respectively, according to the foregoing Japanese patent application laid-open No. 7-202722.
At step ST5, the decision vector [Dk,j] is updated and the soft output vector [Lk] (k=1, 2, . . . , N1) is calculated. The details of step ST5 will be described later.
At step ST6, the differences obtained by subtracting the soft input vector from the soft output vector calculated at step ST5 are stored in the jth column of the correction matrix {W} according to the following Expression (7).Wk,j←Lk−Rk(k=1, 2, . . . , N1)  (7)
At the next step ST7, a decision is made as to whether the value of the counter j is less than N2. If it is less than N2, the value of the counter j is incremented at step ST8, followed by iterating the processing from step ST4 and on. On the other hand, if the value of the counter j is N2, the processing proceeds to step ST9, at which the decoding of the C2 code is started. Up to this time, the update of all the elements of the correction matrix {W} has been completed.
At step ST9, the initial value one is set into the counter i, and the processing proceeds to step ST10. At the next step ST10, ith row of the input matrix {Y} and the ith row of the correction matrix {W} are added element by element. Specifically, according to the following Expression (8), the (i,k) elements Yi,k of the input matrix are added to the (i,k) elements Wi,k of the correction matrix to calculate the soft input values Rk(k=1, 2, . . . , N2).Rk←Yi,k+α×Wi,k (k=1, 2, . . . , N2)  (8)where α is an appropriate normalizing constant.
In the following description, the ith row of the input matrix is denoted by [Yi,k] that of the decision matrix is denoted by [Di,k], and that of the correction matrix is denoted by [Wi,k], which are called input vector, decision vector and correction vector, respectively, as in the decoding of the foregoing C1 code.
At step ST11, the decision vector [Di,k]is updated and the soft output vector [Lk] (k=1, 2, . . . , N2) is calculated. The details of step ST11 will be described later.
At step ST12, the differences obtained by subtracting the soft input vector from the soft output vector calculated at step ST11 are stored in the ith rows of the correction matrix {W} according to the following Expression (9).Wi,k←Lk−Rk (k=1, 2, . . . , N2)  (9)
At the next step ST13, a decision is made as to whether the value of the counter i is less than N1 or not. If it is less than N1, the value of the counter i is incremented at step ST14, followed by iterating the processing from step ST10 and on. On the other hand, if the value of the counter i is N1, the processing proceeds to step ST15. Up to this time, the decoding of the C1 code and C2 code constituting the product code has been completed once.
At step ST15, a decision is made as to whether the decoding of the C1 code is iterated or not. Usually, the decoding is completed when the decoding has been iterated by a predetermined number of times. To iterate the decoding of the C1 code, the processing proceeds to step ST3 to restart the decoding of the C1 code. On the other hand, to stop the decoding, the processing proceeds to step 16, at which the decision matrix {D} is output. Thus, the decoding processing is completed.
The data Di,j (i=1, 2, . . . , K1; j=1, 2, . . . , K2) stored in the K1×K2 decision matrix {D} output at step 16 represent the information data estimated by the decoding. Although the elements of the decision matrix {D} take a value “±1”, the value “+1” corresponds to a binary zero, and “−1” corresponds to a binary one.
Next, the soft input/soft output decoding of the C1 code at step ST5 will be described. FIG. 12 is a flowchart illustrating the details of step ST5.
At step ST21, the soft input vector [Rk] and the decision vector [Dk] are input.
At step ST22, p elements with least absolute values are selected from the soft input vector [Rk]. The positions of the p elements are denoted by k1, k2, . . . , and kp.
At step ST23, a test vector [Tk] is generated whose elements Tkm=0 or 1 at the p positions km (m=1, 2, . . . , p) selected at step ST22, with the remaining elements Tk=0 (k≠km). Since the total of q=2P test vectors are present, they are denoted as [Ts] (s=1, 2, . . . , q) using the suffix s. The resultant test vectors [Ts] and the decision vector [Dk] are added element by element to generate words [Us] given by the following Expression (10) for carrying out algebraic decoding of the C1 code. In Expression (10), the elements “+1” and “−1” of the decision vector [Dk] is converted to a binary zero and one, respectively, and are subjected to modulo-2 addition.[Us]=[Dk]+[Ts](s=1, 2, . . . , q)  (10)
At step ST24, r different candidate codewords [Ct]=(Ct1, Ct2, . . . , CtN1) (t=1, 2, . . . , r) are generated by applying the algebraic decoding of the C1 code to the q words [Us] (s=1, 2, . . . , q) generated at step ST23.
At step ST25, squared Euclidean distances Mt (t=1, 2, . . . , r) are calculated between the soft input vector [Rk] and the candidate codewords [Ct]. The squared Euclidean distance Mt between the soft input vector [Rk] and the candidate codewords [Ct] are given by the following Expression (11).
                              M          t                =                              ∑                          k              =              1                        N1                    ⁢                                    (                                                R                  k                                =                                  C                  k                  t                                            )                        2                                              (        11        )            
At step ST26, the codeword [Cd] that gives the minimum squared Euclidean distance, that is, the codeword [Cd] that satisfies the relationship Mt≧Md (t=1, 2, . . . , r) is selected. In addition, the codeword [Cd] is substituted into the decision vector according to the following Expression (12).[D]←[Cd]  (12)
At step ST27, the counter k is set at its initial value one, and the processing proceeds to step ST28. At step ST28, a decision is made as to whether any candidate codeword [Ct] (t=1, 2, . . . , r) is present, the kth value Ctk of which differs from the kth value Cdk of the codeword [Cd] selected at step ST26, that is, whether the codeword [Ct] that satisfies Ctk=−Cdk is present or not. If it is not present, the processing proceeds to step ST29. If it is present, the processing proceeds to step ST30 at which a codeword that gives the least squared Euclidean distance among such codewords, which is called a concurrent codeword and denoted by [Cc], is selected, and the processing proceeds to step ST31. At step ST29, the soft output values given by the following Expression (13) are calculated.Lk←βCdk  (13)where β is an appropriate normalizing value.
At step ST31, the soft output values given by the following Expression (14) are calculated.Lk←((Mc−Md)/4)Cdk  (14)where Mc is a squared Euclidean distance between the concurrent codeword [CC] and the soft input vector [Rk].
At step ST32, a decision is made as to whether the value of the counter k is less than N1 or not. If k is less than N1, the processing proceeds to step ST33, at which the value of the counter k is incremented by one to iterate the processing from step ST28 and on. On the other hand, if k is equal to N1, the processing proceeds to step ST34, at which the soft output vector [Lk] and the decision vector [Dk] are output, followed by completing the entire processing.
Thus, the soft input/soft output decoding of the C1 code at step ST5 has been completed. Since the soft input/soft output decoding of the C2 code at step ST11 is the same as that of the C1 code, the description thereof is omitted here.
As seen from the foregoing Expressions (13) and (14), the conventional soft output values are calculated using at most two codewords among the candidate codewords generated at step ST24.
With the foregoing configuration, the conventional decoding method of a product code has a problem of being unable to reflect the information provided by the candidate codewords other than the codeword [Cd] and the concurrent codeword [Cc] closest to the soft input vectors in terms of the squared Euclidean distance among the many codewords found at the codeword generating step, thereby being unable to calculate the soft output values accurately.
In addition, it is necessary for the soft output calculation in Expression (14) to calculate the squared Euclidean distances Md and Mc between the soft input vector [Rk] and the candidate codeword [Cd] and the concurrent codeword [Cc]. The amount of calculation of the squared Euclidean distance, however, is large, and this presents a problem of increasing the circuit scale when implementing the calculation by hardware.
Furthermore, since the foregoing decoding method is developed with only the floating-point operation in mind, it has a problem of being unsuitable for the fixed-point operation. In particular, when the demodulation data are represented in terms of the hard decision values and their reliability information, it is necessary to develop a decoding method and a decoding apparatus applicable to them.